1. Field of the Invention
The present invention relates to a method of extending a multistage switch, and more specifically to a method of extending a multistage self-routing (MSSR) switch.
2. Description of the Related Art
Recently, the requests for communications services have diversified, and various services are now being provided to transfer image data including animation data, in addition to voice and data communications services. These services are different from one another in the transmission speed, protocol, etc. of data, and required to be processed in one system. An asynchronous transfer mode (ATM) system has become a practical example of one of the systems for processing these services.
In an ATM network, information in the various services is transferred in fixed length cells. A cell consists of a 5-byte header and a 48-byte payload field. The header stores cell routing information comprising a virtual path identifier (VPI) and a virtual channel identifier (VCI). The payload field stores user information to be transferred.
The cell is transferred through the communications line specified by a VPI/VCI and input to an ATM switch. In the ATM switch, an output VPI/VCI and tag information are retrieved according to the VPI/VCI of the input cell, so that the input VPI/VCI is rewritten to an output VPI/VCI and the tag information is added to the head of the cell. The tag information specifies a path in the ATM switch.
The ATM switch normally consists of a plurality of switching modules. Each switching module forms a matrix of m.times.n switching elements and is connected by a plurality of input and output highways. FIG. 1 shows the configuration of a switching module having a matrix of 8.times.8 switching elements.
When a cell is input to the ATM switch and then input from a predetermined input highway to a switching module, a route in the switching module is automatically selected according to the tag information assigned to the cell, and it is output through the output highway. Thus, since the route of the cell in the switching module is autonomously determined by the cell itself, such a switching module is referred to as a self-routing switching module (SR module).
The ATM switch is normally designed as an MSSR. That is, the SR module is connected to multiple stages. The number of stages of the SR modules depends on the required flexibility in selecting a route in the switch and allowable transmission delay time. For example, a 3-stage configuration is normally adopted. FIGS. 2A through 2H show examples of the schematical configurations of the MSSR switches provided with 3-stage SR modules.
FIG. 2A shows an example of the configuration of the MSSR switch when three SR modules 11 through 13 of the same type are provided for each stage in line. The cell input to the MSSR switch shown in FIG. 2A is output after being switched first by an SR module 11 in the first stage, and then by an SR module 12 in the second stage, and an SR module 13 in the third stage.
The switching capacity of the MSSR switch depends on its configuration. Assuming that, for example, the capacity of the SR module is 20 Gbps, the capacity of the 1-row MSSR switch shown in FIG. 2A is 20 Gbps.
When the capacity of the MSSR switch shown in FIG. 2A is to be extended, one SR module is added to each stage as shown in FIG. 2B to form a 2-row MSSR switch. Thus, the cell input to this MSSR switch is output after being first switched by the SR module 11 or 21 in the first stage, then switched by the SR module 12 or 22 in the second stage, and finally switched by the SR module 13 or 23 in the third stage. Therefore, the capacity of the MSSR shown in FIG. 2B is double the capacity of the configuration shown in FIG. 2A. That is, the capacity can be doubled by reconfiguring a 1-row MSSR switch into a 2-row MSSR switch.
When the switching capacity of the MSSR switch is further extended, SR modules of the same type are added in 3-module units (a module for each stage) to form a 3-row, 4-row, . . . , and 8-row MSSR switches as shown in FIGS. 2C through 2H. Thus, the capacity of the MSSR switch can be extended three times, four times, . . . , and eight times.
Extending the number of the SR modules in each stage of the MSSR switch to increase the number of the rows of the MSSR switch is called the simple extension method.
In the 3-stage MSSR switch, the SR modules are connected by cables between the first stage and the second stage, and between the second stage and the third stage. FIG. 3 shows an example of connecting the 2-row MSSR switch shown in FIG. 2B using cables. Hereinafter, the SR modules are explained as formed by a matrix of 8.times.8 elements as shown in FIG. 1.
As shown in FIG. 3, in the 2-row MSSR switch configured by the simple extension method, eight outputs from each SR module in the first stage are connected to the SR modules 12 and 22 (four outputs to each module) in the second stage. In the example shown in FIG. 3, the SR module 11 is connected to the SR module 12 through cables 101 through 104. The SR module 11 is connected to the SR module 22 through cables 105 through 108. Likewise, eight inputs of each SR module in the third stage are connected to the SR modules 12 and 22 (four outputs to each module) in the second stage.
FIG. 4 shows an example of connecting the 3-row MSSR switch shown in FIG. 2C using cables. In the 3-row MSSR switch, eight outputs (3, 3, and 2 outputs) of the SR modules in the first stage are connected to the three SR modules in the second stage. The connection can be optionally set. In FIG. 4, the SR module 11 is connected to the SR module 12 through cables 101 through 103. The SR module 11 is connected to the SR module 22 through cables 104 through 106. The SR module 11 is connected to the SR module 32 through cables 107 and 108. Similarly, modules are connected between the second and third stages through 2 or 3 cables depending on the positions.
The cables should be reassigned between the first and second stages or the second and third stages when the SR modules 31 through 33 are added to extend the capacity of MSSR switch from the 2-row configuration to the 3-row configuration by the simple extension method, as clearly shown in FIGS. 3 and 4. That is, the cable 104 which connects the SR module 11 to the SR module 12 in the 2-row configuration should be reassigned in the 3-row configuration such that it connects the SR module 11 to the SR module 22. Such cable reassigning operations are also performed not only on the cable 104 but also many other cables. When an already assigned cable is moved, a special technique is required to assure the reliability of the connected points, thereby resulting in complicated processes with an increasing number of cables.
If the above described cable reassigning operation is performed, cell passage routes may be changed. Therefore, the connection admission control (CAC) is performed again on each SR module to reset the route again so that each SR module can be efficiently switched.
Designing the MSSR switch using the simple extension method produces the problem of a block rate. The block rate is described below with reference to FIG. 4.
For example, when a cell is input to the SR module 11 and is to be output to an output highway connected to the SR module 23, the cell can follow three routes through the SR modules 12, 22, or 32.
In the route through the SR module 12, the first stage is connected to the second stage via the three cables 101 through 103, and the second stage is connected to the third stage via the three cables 201 through 203. Since the number of the cables between the first and second stages is the same as that between the second and third stages, a cell transferred from the SR module 11 to the SR module 12 is transferred to the SR module 23 without being discarded.
In the route through the SR module 32, the first stage is connected to the second stage via the two cables 107 and 108, and the second stage is connected to the third stage via the three cables 206 through 208. Since the number of the cables between the first and second stages is smaller than that between the second and third stages, a cell transferred from the SR module 11 to the SR module 32 is transferred to the SR module 23 without being discarded.
In the route through the SR module 22, the first stage is connected to the second stage via the three cables 104 through 106, and the second stage is connected to the third stage via the two cables 204 and 205. Since the number of the cables between the first and second stages is larger than that between the second and third stages, a part of the cells transferred from the SR module 11 to the SR module 22 will be discarded without being transferred to the SR module 23. If it is possible for cells input to the MSSR switch not to be output through the MSSR switch, the logically calculated ratio of the cells which cannot be output to the input cells is referred as the block rate of the MSSR switch.
The block rate of the route from the SR module 11 to the SR module 23 in the above example is calculated as follows, assuming that the SR modules are the same type and an equal band is assigned to each cable.
Block Rate=1-(number of effective cables between second and third stages).div.(number of effective cables between first and second stages) EQU =1-(3+2+2).div.(3+3+2)=0.125 =12.5%
As shown in FIG. 4, the SR module 32 is connected to the SR module 23 via three cables whereas the SR module 11 is connected to the SR module 32 via two cables. If two cables are provided between the SR module 32 and the SR module 23, the cell transferred from the SR module 11 to the SR module 32 can be transferred to the SR module 23 without being discarded. When the cell is routed from the SR module 11 to the SR module 23, two cables can be provided between the SR module 32 and the SR module 23, thereby the number of the effective cables between SR module 32 and SR module 23 being taken as two in the above calculation.
When the block rate of the 3-stage MSSR switch is to be obtained, the above mentioned calculation is performed on the route from any SR module in the first stage to any SR module in the third stage. The maximum value (worst value) of the calculated values is defined as the block rate of the MSSR switch. Table 1 shows the block rate obtained when the 3-stage MSSR switch designed using the simple extension method is extended from the first to eighth rows sequentially.
TABLE 1 ______________________________________ Row Number 1 2 3 4 5 6 7 8 ______________________________________ Block Rate 0% 0% 12.5% 0% 25% 25% 12.5% 0% ______________________________________
When the 3-stage MSSR switch is extended using the simple extension method as shown in Table 1, the block rates of the 1-, 2-, 4-, and 8-row switch indicate 0% whereas the block rates of the 3-, 5-, 6-, and 7-row switch indicate values other than 0%.
If the block rate is not 0%, the use rate of the MSSR switch should be reduced. That is, with the MSSR switch (for example, in the 3-row configuration) having a block rate of 12.5%, if the sum of the bands requested by calls (subscribers) exceeds 87.5% of the switching capacity, then calls may not be established. That is, to guarantee the band of the path in the MSSR switch, the use rate of the switch should be equal to or lower than 87.5%. Therefore, such an MSSR switch should be extended when the sum of the requested bands has reached 87.5% of the switching capacity. Thus, the hardware resources cannot be used efficiently.
As described above, the simple extension method has the demerits that the cables should be reassigned, that the path should be reestablished, and that the resources cannot be used efficiently due to the block rate. To solve these problems, the 2nd-stage full extension method has been developed.
As shown in FIG. 5, the 2nd-stage full extension method refers to the method of providing the largest possible number of SR modules at the second stage of the MSSR switch at the initial implementation. In this example, since each SR module has eight inputs and outputs, eight SR modules 12, 22, 32, 42, 52, 62, 72, and 82 are provided in the second stage.
The configuration shown in FIG. 5 is applied to the MSSR switch having the smallest switching capacity using the 2nd-stage full extension method. The first and third stages are respectively provided with a switching module 11 and a switching module 13. Eight outputs of the SR module 11 are individually connected to the eight SR modules in the second stage. Each output of the eight SR modules is connected to the SR module 13 in the third stage.
When the capacity of the MSSR switch is extended using the 2nd-stage full extension method, an SR module 21 is provided in the first stage and an SR module 23 is provided in the third stage as shown in FIG. 6. Each of the eight outputs of the SR module 21 is connected to the eight SR modules 12, 22, 32, 42, 52, 62, 72, and 82 in the second stage. Each of the outputs of the eight modules is connected to the SR module 23 in the third stage. In FIG. 6, cables from the SR module 11 or to the SR module 13 are omitted for clarity of the figure. The cables shown in FIG. 5 are used as is. When the switching capacity is further extended, the SR modules are added to the first and third stages sequentially, and each of the added SR modules is connected to the eight SR modules in the second stage via cables.
Thus, according to the 2nd-stage full extension method, the SR modules can be extended using only additional cables. That is, it is not necessary to reassign cables between SR modules after removing them from other SR modules. It is also not necessary to redefine a path in the MSSR switch. Since the number of cables between SR modules is same and the connection of the cables between the first and second stages is in symmetry with the connection of the cables between the second and third stages (the second stage shows a regular configuration), the block rate is 0%.
However, according to the 2nd-stage full extension method, more SR modules are required than in the simple extension method. For example, a basically equal switching capacity is required by the 1-row MSSR switch by the simple extension method as shown in FIG. 2A and by the initially-configured (1-row) MSSR switch using the 2nd-stage full extension method as shown in FIG. 5. However, the number of SR modules in the 2nd-stage full extension method is 3.3 times more than that in the simple extension method (3 modules in the simple extension method; and 10 modules in the 2nd-stage full extension method). Since the SR modules are expensive, the 2nd-stage full extension method is less advantageous in cost than the simple extension method.
As explained above, the simple extension method and the 2nd-stage full extension method are adopted in extending the MSSR switch. However, no methods are recommended in consideration of the cost, operability, or efficiency in resources.